/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/movie-recommendation
   @Language: C++
   @Datetime: 20-01-14 13:29
   */

class Solution {
	typedef pair<int,pair<int,int> > Node;
	struct less{
		bool operator()(const Node &a, const Node &b){
			if (a.second.first==b.second.first)
				if (a.second.second==b.second.second)
					return a.first<b.first;
				else return a.second.second>b.second.second;
			return a.second.first>b.second.first;
		}
	};
public:
	vector<vector<int>> minMalwareSpread(vector<vector<int>> &graph) {
		int n = graph.size();
		vector<vector<int> > recommends(n);
		for(int u=0; u<n; ++u){
			unordered_map<int,pair<int,int> > movies;   // movie, freq, weight
			for(int v=0; v<n; ++v){
				if (u==v) continue;
				vector<int> common;
				set_intersection(graph[u].begin(), graph[u].end(),
						graph[v].begin(), graph[v].end(), back_inserter(common));
				if (common.size()==0) continue;
				vector<int> diff;
				set_difference(graph[v].begin(), graph[v].end(), 
						common.begin(), common.end(), back_inserter(diff));
				for(const auto &m:diff)
					movies[m]={movies[m].first+1, movies[m].second+common.size()};
			}
			priority_queue<Node, vector<Node>, less> freqs, cors;
			for(const auto &m:movies){
				freqs.push(m);
				if (freqs.size()>5) freqs.pop();
			}
			for(; freqs.size(); freqs.pop())	// movie, weight, freq
				cors.push({freqs.top().first, {freqs.top().second.second, freqs.top().second.first}});
			for(; cors.size(); cors.pop())
				recommends[u].push_back(cors.top().first);
			reverse(recommends[u].begin(), recommends[u].end());
		}
		return recommends;
	}
};
